1. Field of the Invention
The present invention relates generally to an architecture, apparatus and method for communications in networks, such as ad-hoc networks. More particularly, the present invention relates to a mechanism and architecture through which multiple tables maintained by multiple routing managers can be efficiently handled by a single forwarding module.
2. Background and Related Art
Wireless ad-hoc networks preferably do not rely on base stations or other fixed infrastructure. Accordingly, ad-hoc networks are extremely important in military, emergency and temporary (e.g., business meetings, campaign headquarters, etc.) environments. As will be appreciated by those skilled in the art, in some ad-hoc networks, each node is responsible for routing “packets,” or message signals, for other network nodes. An example of this type of network 100 is shown in FIG. 1a. As illustrated, node X can route packets between nodes W, Y and Z, for example. Nodes in an ad-hoc network preferably employ known routing protocols to accomplish their routing requirements.
For example, as discussed in U.S. Pat. No. 6,028,857, issued to R. Poor on Feb. 22, 2000, and assigned to the Massachusetts Institute of Technology, in a “link state” routing approach, each network node maintains a routing table that specifies an “optimal” path toward each network destination. In the U.S. Pat. No. 6,028,857 the term “optimal” is used to generally mean the shortest path, but may account for other factors such as load balancing.
As will be appreciated by those skilled in the art, a shortest-path calculation can be performed via a shortest-path first algorithm, for example, Dijkstra's algorithm as explained in Chapter 5 of “Routing in Communications Networks,” M. Steenstrup, ed., 1995. As will also be understood by those skilled in the art, many other procedures exist for routing messages over a network, even when a configuration of the network may change. There are also many procedures for measuring or rating the connectivity of a network in a particular configuration (e.g., metric generation) that are well known in the art.
As discussed in the U.S. Pat. No. 6,028,857, when a node in a link state routing system transmits a message to a destination node, it first fetches from a routing table an entry for the specified destination. The routing table entry specifies which neighbor of an originating node should relay the message and the identification of that neighbor is installed in a message header as the recipient. The originating node then transmits the message. Many of the originating node's nearby neighbors receive the message, since radio frequency (“RF”) transmissions are essentially omni-directional. However, of all the neighbors that receive the transmission, only the specified recipient acts on the message. The recipient relays the message in the same manner, according to an entry in its routing table corresponding to the destination node. This process continues until the message reaches the ultimate destination. The nodes in the U.S. Pat. No. 6,028,857, however, do not maintain these types of routing tables, but rather maintain “cost tables” that indicate the costs of transmission to other nodes in the network.
Other forms of ad-hoc wireless networks simplify routing and minimize routing traffic by organizing nodes (e.g., network members) into hierarchical groups called clusters, with each cluster having a cluster head. A cluster may include a single cluster head and zero or more cluster members. A cluster head represents affiliated cluster members to the network. Cluster head stations communicate with each other to form a network backbone, and cluster member stations relay messages to the network through affiliated cluster heads. In mobile systems, cluster members move into and out of clusters depending on their physical location and radio connectivity. An example of this type of mobile communications network 110 is shown in FIG. 1b, in which areas 1a, 1b and 1c represent individual clusters. In FIG. 1b, a double-circle indicates a Cluster Head (“CH”), whereas a single circle indicates a Cluster Member (“CM”). In the FIG. 1b example, CM2 and CM3 are affiliated with a cluster headed by CH1, and CM6 and CM7 are affiliated with a cluster headed by CH5. CH4 is the head of its own cluster, and does not have any currently affiliated cluster members.
Another example of a mobile communications network is disclosed in U.S. Pat. No. 5,850,592, issued to S. Ramanathan on Dec. 15, 1998, and assigned to the same assignee of this present application. The U.S. Pat. No. 5,850,592 discloses a method for a plurality of mobile stations to automatically organize them into a hierarchical network, in which some of the stations operate as message gateways for a cluster of mobile stations. Initially, mobile stations search for available cluster heads and initiate an affiliation procedure to establish them as cluster members. If the affiliation procedure is successful, a mobile station operates as a cluster member. Otherwise, a mobile station promotes itself to operate as a cluster head.
In the arrangement of the U.S. Pat. No. 5,850,592, each station operates in at least two basic modes. In the first mode, the mobile station serves as a message gateway for a cluster of other member stations. The second mode allows the mobile station to operate as a non-gateway (or “cluster member”) station. Each mobile station determines which out of the two modes to operate in, as discussed above. The mobile stations disclosed in the U.S. Pat. No. 5,850,592 can operate at two different power levels. When there are no other available cluster heads, a mobile station operates as a cluster head, and transmits at a relatively high power level. A cluster head transmits at the relatively high power level to communicate with other cluster head stations and to typically provide longer distance network links. Although a cluster head communicates at a higher power level with other cluster heads, a cluster head can still communicate with its cluster members using a relatively lower power level.
One object of these types of ad-hoc networks is to route packets from an originating node to a destination node (or nodes). As will be appreciated by those skilled in the art, there are various operational modes or types of routing that can be used to accomplish this objective. For example, “broadcast” routing directs a packet to all network destinations simultaneously, whereas “multicast” routing directs a packet only to a well-defined group of nodes. “Unicast” (or point-to-point) routing directs a packet from an originating node to a single network destination.
Known system architectures typically employ a complexly interwoven routing manager (e.g., a software module) and forwarding layer to support either broadcast, multicast or unicast routing. These prior techniques typically create “stove-piped” solutions, meaning that a single forwarding layer is built for a single routing manager and a particular radio device. Porting this type of architecture to a new radio, or modifying the routing mechanisms, results in significant time, cost and complexity. With known system architectures, it is difficult, if not impossible, to support multiple routing schemes within a mobile radio station.
A radio frequency (RF) device that is typically a part of a wireless communications node generally has competing interests that produce performance trade-offs. Power, data rate, spread spectrum chipping code rate, and error correction methods are just a few examples of these different interrelated interests. As will be appreciated by those skilled in the art, often a selection of a value for one of these interests is not independent among the many interests present in a mobile radio and may have consequences for the network as a whole. For example, increasing the power for a particular transmission increases signal reliability, but may also drain a battery at a sending (or source) node and/or may cause more interference at other local network nodes. Accordingly, a problem exists in that a type-of-service (or a “quality or service”) for a particular transmission must be balanced and integrated with a particular routing scheme and the radio parameters used for transmission (e.g., power, data rate, etc.).
These types of problems are not adequately addressed in the art. Thus, there is a need for a wireless packet router that seamlessly maintains multiple forwarding tables and radio parameters necessary to support quality of service guarantees. There is another need for an architecture that enables multiple routing mechanisms to co-exist with a single forwarding layer. There is also a need to handle quality of service mechanisms across different routing mechanisms in a packet radio router. There is a further need for a forwarding layer that allows extensive modification of radio parameters on a packet-by-packet basis, but does not require the forwarding layer to know the details of the particular radio layer. There is also a need for compact and efficient routing mechanisms and/or tables, and for a method for forwarding table decomposition.